package recursion;

import java.util.Set;

/**
 * @author kaho
 * @since 2020/12/21
 */
public class 上楼梯 {


    public static int 上楼梯(int n) {
        if (n < 3) {
            return n;
        }
        return 上楼梯(n - 1) + 上楼梯(n - 2);
    }


    public static int 上楼梯1(int n) {
        if (n < 3) {
            return n;
        }
        int s1 = 1, s2 = 2;
        for (int i = 3; i <= n; i++) {
            s2 = s2 + s1;
            s1 = s2 - s1;
        }
        return s2;
    }


    public static int step(int n) {
        return tailRecursion(n, 1, 2);
    }

    private static int tailRecursion(int n, int fist, int second) {
        if (n == 1) {
            return fist;
        }
        if (n == 2){
            return second;
        }
        return tailRecursion(n - 1, second, second + fist);
    }

    public static void main(String[] args) {
        int s = 3;
        System.out.println(step(s));
        System.out.println(上楼梯1(s));
        System.out.println(上楼梯(s));
    }

}
